The synthesis of realistic images in three dimensional computer graphics requires the evaluation of a shading model simulating the propagation of light within a scene or environment. In the prior art, local shading models have been employed wherein shading is computed based only on direct illumination by light sources. Synthesis of realistic shading, and hence of realistic images, however, requires the use of a global illumination model in which secondary illumination provided by light reflected from other sources in the scene, and the shadowing of one surface by another, are taken into account.
A number of global illumination techniques for generating three dimensional computer graphics are known, the most common of which are ray tracing and radiosity. The following publications, which are incorporated herein by reference, are illustrative: Goral, Cindy M. et al., "Modeling the Interaction of Light Between Diffuse Surfaces", Computer Graphics, vol. 18, no. 3, pp. 213-222 (July, 1984); Cohen, Michael F. et al., "The Hemi-Cube: A Radiosity Solution For Complex Environments", SIGGRAPH Proceedings, vol. 19, no. 3, pp. 31-40 (1985); Greenberg, Donald P. et al. "Radiosity: A Method For Computing Global Illumination", The Visual Computer, vol. 2, pp. 291-297 (1986); Cohen, Michael F. et al., "An Efficient Radiosity Approach For Realistic Image Synthesis", IEEE CG&A, pp. 26-35 (March, 1986); Cohen, Michael F. et al., "A Progressive Refinement Approach to Fast Radiosity Image Generation", Computer Graphics, vol. 22, no. 4, pp. 75-84 (August, 1988). See also the following publications, incorporated herein by reference, which describe various ray tracing techniques: Maxwell, Gregory M. et al., "Calculation of the Radiation Configuration Using Ray Casting", Computer Aided Design, vol. 18, no. 7, pp. 371-379 (September 1986); Arvo, James, "Backward Ray Tracing", Apollo Computer, Inc. Chelmsfor, Mass. (date unknown); Cook, Robert L. et al., "Distributed Ray Tracing", Computer Graphics, vol. 18, no. 3, pp. 137-145 (July, 1984); Chattopadhyay, Sudeb et al., "Bi-Directional Ray Tracing", Proceedings of Computer Graphics 1987, pp. 335-343 (1987).
Ray tracing approximates the global illumination of a scene by tracing rays from the eye through a viewing plane and into the three dimensional environment. For each ray, the closest surface intersection point is determined. Depending upon the material properties of the surface, it may spawn reflected and refracted rays, which are recursively traced in the same fashion. As the spawned rays are propagated through the environment, a tree of intersection locations is constructed for each sample point on the viewing plane. The final image intensity of this point is determined by traversing the tree and computing the contribution of each node according to a shading model.
The intensity calculation for each node consists of two parts. The first part determines if the intersection point can be seen from each light source. If no opaque object blocks the light from the intersection point, then the second part consists of using the attributes of the surface and the light source to calculate the contribution to the final color intensity of the pixel.
The first operation, called "shadow testing", is normally the most computationally expensive process of the ray tracing technique. The reason for this is that each object in the entire environment must be tested to determine if it occludes each light source for every ray intersection point. For scenes with complex lighting schemes, the percentage of time required for occlusion testing can increase to over 80% of the total computation time.
Thus, ray tracing techniques can be slow and in any event suffer from the disadvantage that they are view dependent, i.e., the scene must be recreated for each new view.
The advantage of the radiosity technique is that it is view independent. The radiosity technique consists of a series of independent steps. First, the geometry, surface color and surface reflectance properties of the object in the scene are specified and stored in a data base. Each surface is subdivided into a number of discrete surface patches for which a constant intensity or radiosity is assumed. The geometric relationship between each patch and the environment to every other patch is next determined, resulting in a system of simultaneous equations. Solving these equations yields the radiosity for each patch. Finally, the radiosity information is used to render an image of the environment from any given view point.
Calculating the geometry relationships, or form factors, between patches, is the most computationally expensive part of the radiosity technique for complex environments (i.e., environments where some patches may fully or partially occlude others). Thus, despite the advantage of view independence, the radiosity technique has been considered impractical for scenes of high complexity; the time and storage costs of the algorithm were expensive (i.e., O(n.sup.2), where n is the number of surfaces in the scene).
Another rendering technique is known as progressive radiosity. Progressive radiosity is a refinement upon the basic radiosity technique and provides good synthetic images early in the solution process. In the progressive radiosity technique, illumination is computed one step at a time. At each step, the reflected or emitted illumination provided by a single source is distributed to all other surfaces. The determination of where the illumination falls in the scene is accomplished using the well known "hemi-cube" algorithm, (see, e.g., the above referenced Cohen et al. publication relating to the hemi-cube), in which the scene is scan converted from the point of view of the surface providing the illumination. In effect, light is "shot out" from the source in a predefined uniform set of directions to land where it may in the environment. Although the overall progressive radiosity technique provides improvements over prior radiosity techniques for graphics, the use of the hemi-cube algorithm to determine illumination suffers inherently from aliasing and undersampling, particularly as the scene complexity increases.
The present invention employs an improvement to the progressive radiosity technique and, therefore, additional detail respecting the underlying physics and mathematics of the progressive radiosity technique is provided herein as background.
As mentioned, the original radiosity technique determines diffuse global illumination by solving a system of equations expressing the dependence of the energy leaving each surface and that arriving from every other surface. The energy leaving a surface is determined according to the following relationship: ##EQU1## where B.sub.i =radiosity of surface i (energy per unit area)
A.sub.i =area of surface i PA1 E.sub.i =emitted energy per unit area PA1 P.sub.i =reflectivity of surface i PA1 B.sub.j =radiosity of surface j PA1 A.sub.j =area of surface j PA1 F.sub.ji =form-factor from surface j to surface i PA1 do [the following steps] until the image is converged:
The form-factor, F.sub.ji, is the fraction of energy leaving surface j that arrives at a second surface i.
An equation of this form exists for every surface in the scene. The resulting system of simultaneous equations can be solved using conventional matrix techniques to determine the surface radiosities. A known shading calculation then uses these surface radiosities to determine the radiosity at the vertices of smaller polygonal elements into which the surfaces have been subdivided. (The elements are actually defined by vertices of the polygons.) Following the radiosity solution, Gouraud interpolation based on the element vertex radiosities can be used to render smoothly shaded images.
Forming the matrix prior to the solution requires determining and saving the form factor between each surface and every other surface, a process that is expensive (O(n.sup.2)) both in time and memory requirements. The progressive radiosity technique overcomes this difficulty by solving the radiosity equations in a series of steps. The solution proceeds as follows:
1. select the surface with the greatest reflected and/or emitted energy (i.e., the surface having the greatest irradiated light energy); PA2 2. compute the form-factors from that surface to all surface elements; and, PA2 3. add the resulting contribution to the radiosity of each element.
In the prior art, the form-factors from the source surface to the receiving elements are computed using the well known hemi-cube technique, in which all elements are projected, scan converted and z-buffered onto the five faces of a hemi-cube positioned at the source surface. In the early steps, the surfaces chosen will be the light emitters since other surfaces will have, as yet, received very little illumination. Subsequent steps will select secondary sources, starting with those surfaces that received the most light directly from the light sources, and so on.
Since each solution step updates the radiosity of all surfaces, an increasingly accurate result can be displayed following each step. An ambient term derived from the known energy yet to be distributed can be added to improve the image. Useful images can thus be produced very early in the solution process. There are, however, inherent problems in using a hemi-cube placed at the source surface to determine form factors. These are discussed below.
The source of efficiency in the progressive radiosity algorithm is that illumination is computed roughly in the order that light propagates through the environment. In effect, the path of light is followed from the light emitters into the scene.
The more common strategy for computer graphics, however, is to start at the eye and trace the light back to the source. This has the advantage of restricting shading effort to those points in the scene that appear in the image and to the directions that reach the eye. Ray tracing and its derivatives, distributed ray tracing and path tracing, employ this approach. However, these methods do not have information about where in the scene to look for important sources of light, other than the light emitters themselves. Hence, for a diffuse surface, much sampling may be expended on directions from which little energy turns out to arrive.
By reversing the process and following the propagation of energy from the emitters, progressive radiosity continually has information about where the energy arrives from. Attention can thus be focused on the most important surfaces of illumination. Even very small secondary sources that nonetheless happen to reflect a great deal of light will be detected, a very difficult case when working entirely from the eye by ray tracing.
The foremost difficulty with the hemi-cube approach employed in progressive radiosity is uneven and inadequate sampling. A surface that is fairly large in the image may, when viewed from the light source, be small enough to fall between the hemi-cube pixels. Such a surface will receive no illumination. FIG. 1 illustrates this problem. FIG. 1 illustrates a portion of a scene having surfaces A, B and C and a source S over which a hemi-cube H has been superimposed. As shown, the hemi-cube is divided into pixels PI. Surfaces A, B and C are all substantially the same size. Surface A covers two hemi-cube pixels (rays R1 and R2) while surface B covers only pixel (ray R4). Surface C drops out entirely and therefore incorrectly receives no illumination. In addition, since the hemi-cube is a uniform sampling method, it will produce aliasing. The shading of a fine grid of small polygons (defined by the vertices) will show a distinct plaid pattern if the polygons are small enough to alias on the hemi-cube. FIG. 2 schematically illustrates this phenomenon in two dimensions. As shown in FIG. 2, a surface patch P consisting of a grid of polygons (defined by the polygon or "element" vertices) is illuminated by a small light source S. The rectangular hemi-cube sampling pattern interacts with the regular receiving grid of polygons to generate aliasing. Increasing the resolution of the hemi-cube to reduce these effects becomes expensive in terms of both computation time and storage, and, in any case, can never guarantee adequate sampling for all polygons.
There are additional problems with the progressive radiosity technique that employs the hemi-cube approach. First, in the radiosity method, light sources are normally surfaces with area. Performing a single hemi-cube at a surface is equivalent to treating the surface as a point source. To approximate an area source, hemi-cubes must be performed at several points on the surface. However, the number of points necessary for a good approximation depends upon how close the area is to the surface it illuminates. Employing the hemi-cube approach, the number of points representing the source area will be the same for all receiving surfaces, since all surfaces are projected onto each hemi-cube.
A further serious limitation derives from the fact that a hemi-cube placed over the light source determines the energy received by source areas (the elements), not points on the surface. Since it is actually the shading at element vertices that is used in rendering the final image, the radiosity at each vertex must be determined by averaging the radiosity of the elements surrounding it. This requires connectivity information that is not always available. Similarly, smooth shading of curved surfaces which are approximated by independent polygonal facets also requires connectivity information when the hemi-cube is used. Continuity of shading across such surfaces is normally ensured by calculating shading at the facet vertices using the true surface normal, as in Gouraud shading. Using the hemi-cube approach, radiosities can be determined directly only for each facet and averaging must be performed to obtain vertex shading.
It is therefore desirable to provide a method of rendering a three-dimensional, computer generated, graphics image that attains the benefits of both progressive radiosity and ray tracing, but avoids the problems inherent in employing the hemi-cube approach. It is also desirable to provide a method for generating a three dimensional image that is less costly in terms of computational time and storage than the conventional progressive radiosity technique. The present invention achieves these objectives.